V dnešnej dobe programovanie utrieďovacích algoritmov prakticky nemá zmysel, nakoľko všetky dnes vyvíjané aplikácie používajú databázové systémy, ktoré majú tieto funkcie priamo integrované. Napriek tomu nezaškodí poznať princíp fungovania týchto funkcií.
Pri triediacich algoritmoch sa najväčší dôraz kladie na rýchlosť použitej metódy. Vlastnosť algoritmu, ktorá je nepodstatná pri triedení malej hŕstky dát je veľmi dôležitá pri triedení veľkého množstva záznamov, ktorých počet nezriedka prekračuje milióny. Z tohto dôvodu sa utrieďovacie algoritmy píšu priamo v asm-ku. Pre potreby tohto článku som použil jazyk c++.
Do skupiny algoritmov na triedenie dát patria aj funkcie na abecedné zoraďovanie (polí). V praxi sa často používajú funkcie, ako napríklad usort. V prostredí jazyka sql používame parameter order by príkazu select.
Existuje viacero spôsobov fungovania zoraďovacích algoritmov:
Spôbob prvý: Triedenie výberom (triedenie pomocou minima)
Princípom algoritmu je hľadanie prvku s najmenšou hodnotou, a následný presun tohoto prvku na prvú pozíciu.
1. krok: V danej množine prvkov nájdeme prvok s najmenšou hodnotou, a vymeníme ho s prvým prvkom. Touto operáciou dosiahneme, že na prvom mieste vybranej množiny bude vždy najmenší prvok
2. krok: Z množiny prvkov "vypustíme" prvok na ľavej strane, a opakujeme 1. krok.
Opakovaním tohto cyklu sa množina zmenšuje vždy o jeden "práve utriedený" prvok. Cyklus končí, keď je množina prázdna.
Utrieďovací algoritmus je znázornený na nasledujúcom obrázku:
Schematické znázornenie 1. metódy triedenia
Nasleduje algoritmus vo forme funkcie v céčku. Vstupom funkcie je neutriedené pole prvkov, a počet prvkov, ktoré sa majú zoradiť. Výstupom je ukazovateľ (pointer) na utriedené pole v operačnej pamäti:
int *zoradit1(int arr[], int n) {
for (int k=0; k<n-1; k++) // zmenšenie množiny
for (int j=k+1; j<n; j++)
if (arr[k]<arr[j]) {
int temp=arr[k];
arr[k]=arr[j];
arr[j]=temp;
}
return arr;
}
S menšou obmenou môže algoritmus pracovať ešte rýchlejšie. V premennej m si algoritmus zapamätá index najmenšieho prvku pri každom znížení počtu prvkov aktívnej množiny
int *zoradit2(int arr[], int n) {
for (int k=0;k<n-1;k++) { // zmenšenie množiny
int m=k; // m = index najmenšieho prvku
for (int j=k+1;j<n;j++)
if (m!=k) {
int temp=arr[m];
arr[m]=arr[j]; arr[j]=temp;
}
}
return arr;
}
Záver: Algoritmus má pre n prvkov (n-1)! opakovaní. Pre 10 prvkovú množninu toto číslo predstavuje hodnotu 362880, čo je už značné množstvo.
Zotrieďovacie funkcie si môžete vyskúšať v tejto ukážke:
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
// tu budu definované zotrieďovacie funkcie
void main() {
int i, n=6;
// n = počet prvkov poľa
int pole[] ={1,5,66,58,11,54};
// pole naplníme vzorovými hodnotami
int *pointer=zoradit1(pole, n);
for (i=0;i<=n;i++) {
cout << *pointer << "\n";
*pointer++;
}
}